As is well known in the art, digital signal processing is now commonly used in many electronic systems, over a wide range of applications. Digital signal processing is utilized in video and audio signal processing, such as used in image recognition, image processing, data compression, digital audio and digital video recording and playback, and the like. Digital signal processing techniques are particularly commonplace in telecommunication applications.
Within the field of telecommunications, mobile communications are becoming particularly popular. The recent revolution in digital processing has enabled a rapid migration of mobile wireless services to digital communications, such as cellular telephone services provided via code division, multiple access (CDMA) technology. Increasingly, development efforts are focusing on techniques for high-capacity communication of digital information over wireless links, and much of this broadband wireless development work incorporates spread-spectrum communications similar to those used in CDMA.
Digital signal processing, including the processing for spread-spectrum wireless communications makes considerable use of digital filters. Digital filtering involves processing of sampled-data, or discrete-time, signals in accordance with a filtering algorithm. Stated another way, a digital filter utilizes a computational process, carried out either through dedicated hardware or through the execution of a sequence of instructions by programmable logic, by way of which an input sequence of numbers representing discrete signal samples is converted into an output sequence of numbers, modified by the transfer function of the desired filter.
For example, U.S. Pat. No. 6,112,218 to Gandhi et al. discloses a digital filter in which addition operations are interleaved among first and second output sample values, so that the resulting addition may be carried out with adder circuitry of the same precision as the signal input and the signal output.
In present day communication devices, digital filters are favored for their ease of implementation, efficient operation and good performance. Such filters can be built using off the shelf components such as digital signal processors (DSPs), custom designed using digital logic elements or implemented using read only memory (ROM) based table look-up techniques. Many functions may be implemented using such digital filters. In a wireless receiver, for example in a base station or a remote/mobile terminal device, such filters may be used for filtering received signals before further processing to recover transmitted data.
For example, U.S. Pat. No. 5,784,419 to LaRosa et al. discloses a digital filter, suitable for use in a CDMA communication device, which uses coefficient precombing. The digital filter includes a coefficient storage circuit, for storing the precombined coefficients, and a selection circuit for selecting appropriate precombined coefficients in response to the input signal. A circuit combines the appropriate coefficients, to produce a filtered signal.
The transfer function of any digital filter, including any digital filter used in wireless communications, can be written in the following form:                               y          ⁡                      (            n            )                          =                                            ∑                              l                =                1                            M                        ⁢                                                  ⁢                                          a                l                            ·                              y                ⁡                                  (                                      n                    -                    i                                    )                                                              +                                    ∑                              l                =                0                            N                        ⁢                                                  ⁢                                          b                l                            ·                              x                ⁡                                  (                                      n                    -                    i                                    )                                                                                        (        1        )            
Such a filter function can be implemented by canonical form, for example by the hardware illustrated in FIG. 1. The illustrated filter 10 includes a section 11, for processing of the digitized samples of the input signal x. As shown, the input signal x(n) is applied to a first multi-tap delay line formed of delay elements 131 to 13N. Each delay element 13 provides a delay of one clock interval Z−1, which typically corresponds to the inter-symbol time period for the wireless digital communication system. The section 11 includes a number N+1 of multipliers 15, shown as multipliers 150 to 15N. Stated another way, the filter section 11 includes one such multiplier 150 to 15N for receiving each of the N+1 input samples, from the x(n) input and from the N taps between and after the delays 131 to 13N of the delay line.
Each multiplier 15 multiplies the respective sample from the input or the delay line by a corresponding coefficient value b. Hence, the multipliers 150 to 15N multiply the sample values for x(n) to x(n−N) by the respective coefficient values b0 to bN. A series of adders 171 to 17N accumulate the outputs of the multipliers 150 to 15N. Stated another way, the adders accumulate the total of the products from the mutiplications of the sample values times the first set of coefficients, over time intervals 0 to N.
The adder 17N also adds the feedback signal from a second section 19, of the digital filter 10, to form the overall filter output y(n). In a wireless spread-spectrum receiver, for example, the adder 17N supplies the accumulated output value to circuitry of the digital demodulator, for further processing.
The second section 19 of the digital filter 10 processes the digitized samples of the output signal y. As shown, the output signal y(n) is applied to a second multi-tap delay line formed of delay elements 211 to 21M. Each delay element 21 provides a delay of one interval Z−1. The section 19 includes a number M of multipliers 23, shown as multipliers 231 to 23M. Stated another way, the second filter section 19 includes one such multiplier 231 to 23M for receiving each of the delayed output samples y and the M taps between and the delays 211 to 21M of the second delay line. In many applications, M will equal N+1.
Each multiplier 23 multiplies the respective sample from the delayed output by a corresponding coefficient value a. Hence, the multipliers 231 to 23M multiply the output sample values for y(n−1) to y(n−M) by the respective coefficient values a1 to aM. A series of adders 25 accumulate the outputs of the multipliers 23. Stated another way, the adders accumulate the total of the products from the mutiplications of the delayed output sample values times the second set of coefficients, over time intervals 1 to M. The series of adders 25 supply this total as the feedback signal to the adder 17N, to produce the overall filter output y(n).
As shown by the exemplary hardware diagram of FIG. 1, the filter function expressed in Equation (1) requires a large number of multiplications. If implemented in a digital signal processor, this requires a large number (N+M) of multiplications during each clock cycle. If implemented in hardware, the N+M multipliers require a large number of gates and consume a large amount of power.
For example, current proposals for the digital filter in fourth generation wireless systems may require 60 or more multiplications every clock cycle. With a DSP implementation, such a performance level is difficult to achieve at both the desired processing speed and reasonable cost and power dissipation levels for wireless applications, particularly for applications in portable wireless equipment. A hardware implementation can achieve the performance, but such an implementation requires an excessive number of gates and consumes an excessive amount of power, which reduces the time before recharging the battery of the portable equipment.
For wireless communications and other applications there is a need for digital filters that can be implemented with a minimum number of multiplication operations, so as to reduce complexity of operation, to reduce the amount of necessary hardware and to reduce power consumption. Hence, there is a continuing need for a digital filter methodology which implements a filter function that can achieve computations equivalent to a substantial number of multiply operations but without using actual multiplications.